package chapter15;

/**
 * 动态规划-子序列
 * <p>
 * LCS:最长公共子序列
 * 思想：线性数组转矩阵
 * 例如：X=[a,b,c,c,c,d,c,c],Y=[a,b,c,c,c,d,c,c]
 * 转矩阵：
 * 0 0 a b c c c d c c
 * 0 0 0 0 0 0 0 0 0 0
 * a 0 1 1 1 1 1 1 1 1
 * b 0 1 2 2 2 2 2 2 2
 * c 0 1 2 3 3 3 3 3 3
 * c 0 1 2 3 4 4 4 4 4
 * c 0 1 2 3 4 5 5 5 5
 * d 0 1 2 3 4 5 6 6 6
 * c 0 1 2 3 4 5 6 7 7
 * c 0 1 2 3 4 5 6 7 8
 * <p>
 * 例如：X=[a,b,c,c,c,d,c,c],Y=[c,c,d,c,c,c,b,a]
 * 转矩阵：
 * 0 0 a b c c c d c c
 * 0 0 0 0 0 0 0 0 0 0
 * c 0 0 0 1 1 1 1 1 1
 * c 0 0 0 1 2 2 2 2 2
 * d 0 0 0 1 2 2 3 3 3
 * c 0 0 0 1 2 3 3 4 4
 * c 0 0 0 1 2 3 3 4 5
 * c 0 0 0 1 2 3 3 4 5
 * b 0 0 1 1 2 3 3 4 5
 * a 0 1 1 1 2 3 3 4 5
 *
 */
public class LCS {

    public static int[][] LCSLength(String[] X, String[] Y) {
        int m = X.length;
        int n = Y.length;
        int[][] c = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (X[i - 1].equals(Y[j - 1])) {
                    c[i][j] = c[i - 1][j - 1] + 1;
                } else {
                    c[i][j] = Math.max(c[i - 1][j], c[i][j - 1]);
                }
            }
        }
        return c;
    }

    public static int memoizedLCSLength(String[] X, String[] Y, int i, int j, int[][] c) {
        if (i == 0 || j == 0) {
            return 0;
        }
        if (c[i][j] > 0) {
            return c[i][j];
        }
        if (X[i - 1].equals(Y[j - 1])) {
            return c[i][j] = memoizedLCSLength(X, Y, i - 1, j - 1, c) + 1;
        }
        return c[i][j] = Math.max(memoizedLCSLength(X, Y, i - 1, j, c), memoizedLCSLength(X, Y, i, j - 1, c));
    }

    public static void printLCS(int[][] c, String[] X, int i, int j) {
        if (i < 1 || j < 1) {
            return;
        }
        if (c[i - 1][j - 1] < c[i][j] && c[i - 1][j] < c[i][j] && c[i][j - 1] < c[i][j]) {
            printLCS(c, X, i - 1, j - 1);
            System.out.print(X[i - 1]);
        } else if (c[i - 1][j] == c[i][j]) {
            printLCS(c, X, i - 1, j);
        } else {
            printLCS(c, X, i, j - 1);
        }
    }

    public static void printLCSSolution(String[] X, String[] Y) {
        int[][] c = LCSLength(X, Y);
        printLCS(c, X, X.length, Y.length);

        int m = X.length;
        int n = Y.length;
        int[][] c1 = new int[m + 1][n + 1];
        memoizedLCSLength(X, Y, X.length, Y.length, c);
        printLCS(c1, X, X.length, Y.length);
    }

}
